Pengantar Algoritma Genetik: Kerangka Kanonik dan Kode Nyata

Algoritma Genetik (GA) adalah heuristik pencarian global stokastik yang terinspirasi oleh prinsip evolusi alamiah, khususnya "kelangsungan hidup yang paling kuat" menurut Darwin dan rekombinasi genetik.

1. Kerangka Representasi

GA Kanonik: Gunakan representasi string biner atau Gray untuk mengkodekan variabel keputusan.
GA Kode Nyata (RCGA): Manipulasi langsung vektor titik mengambang, sering kali lebih efisien untuk optimasi kontinu.

2. Siklus Evolusioner

Proses iteratif evaluasi, seleksi, dan reproduksi. Konsep penting adalah perbedaan antara Genotipe (string bit yang dienkripsi/kromosom) dan Fenotipe (nilai variabel keputusan yang didekripsi dalam ruang masalah sebenarnya).

Pemetaan dari string biner ke nilai nyata $x \in [a, b]$ diberikan oleh:

$$x = a + \frac{nilai\_desimal \times (b - a)}{2^L - 1}$$

Di mana $L$ adalah panjang bit kromosom.

Tebing Hamming

Perhatikan Tebing Hamming dalam pengkodean biner standar—keadaan di mana angka desimal bersebelahan (seperti 7 dan 8) memiliki pola bit biner yang sangat berbeda (0111 vs 1000), membuat GA kesulitan melakukan pencarian lokal.

Implementasi Python: Dekode Biner ke Nyata

Pertanyaan 1

Mengapa pengkodean Gray sering lebih disukai dibandingkan pengkodean biner standar pada GA?

Membutuhkan lebih sedikit memori untuk menyimpan kromosom.

Memastikan bahwa nilai-nilai yang berdekatan hanya berbeda satu bit (Sifat Ketetanggaan).

Secara otomatis menormalisasi nilai antara 0 dan 1.

Secara alami meningkatkan tingkat mutasi.

Pertanyaan 2

Jika probabilitas mutasi (p) diatur terlalu tinggi (misalnya, p = 0.5), apa hasil yang mungkin terjadi?

Algoritma cepat konvergen ke optimum global.

GA berperilaku seperti pencarian acak.

Studi Kasus: Optimalisasi Komponen Jembatan

Baca skenario di bawah ini dan jawab pertanyaannya.

Anda sedang mengoptimalkan desain komponen jembatan di mana variabel keputusan adalah "Ketebalan Material".

Ketebalan harus antara 0,0 mm dan 10,23 mm.
Anda menggunakan GA Kanonik dengan representasi string biner 10-bitrepresentasi string biner.

1. Jika individu memiliki kromosom 0000000000, berapa ketebalan yang didekripsi?

Jawaban: 0,0 mm
String biner 0000000000 sama dengan 0 dalam desimal. Dengan rumus $x = a + \frac{desimal \times (b-a)}{2^L - 1}$, kita dapatkan $0,0 + \frac{0 \times (10,23 - 0,0)}{1023} = 0,0$.

2. Hitung presisi pencarian (perubahan terkecil yang mungkin pada ketebalan) untuk pengaturan 10-bit ini.

Jawaban: 0,01 mm
Presisi didefinisikan sebagai rentang dibagi nilai desimal maksimum. $\frac{10,23 - 0}{2^{10} - 1} = \frac{10,23}{1023} = 0,01\text{mm}$.

3. Selama seleksi, Individu A memiliki kebugaran 10 dan Individu B memiliki kebugaran 30. Dengan seleksi Roda Roulette, berapa peluang B dipilih dibandingkan A?

Jawaban: 75%
Total kebugaran = $10 + 30 = 40$. Peluang memilih B = $\frac{30}{40} = 0,75$ atau 75%. (Rasio 3:1).